// 与L62不同路径相比，网格中多了障碍物

class Solution {
 public:
  // 1. dp[i][j]为走到(i,j)时的路径总数
  // 2. dp[i][j]=dp[i-1][j]+dp[i][j-1]; 前提obstacleGrid[i][j]不为1
  // 3. dp[*][0]=1,dp[0][*]=1; 将其中obstacleGrid[..][..] == 0，置dp[..][..]为0
  // 4. i:0->m,j:0->n. 从左到右一层一层遍历
  // 5. 检查dp数组
  /*
  int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
      int m = obstacleGrid.size();
      int n = obstacleGrid[0].size();
      vector<vector<int>> dp(m,vector<int>(n,0));  // dp数组初始值就全为0了
      int i,j;
      for (i = 0; i < m && obstacleGrid[i][0] == 0; i++) dp[i][0] = 1;
      for (j = 0; j < n && obstacleGrid[0][j] == 0; j++) dp[0][j] = 1;
      for(i=1;i<m;i++) {
          for(j=1;j<n;j++) {
              if(obstacleGrid[i][j]==0)
                  dp[i][j]=dp[i-1][j]+dp[i][j-1];
          }
      }
      return dp[m-1][n-1];
  }
  */
  // TODO: 思考一下！
  // 二维dp数组空间优化
  int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
    int n = obstacleGrid.size(), m = obstacleGrid[0].size();
    vector<int> f(m, 0);

    f[0] = (obstacleGrid[0][0] == 0);
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < m; ++j) {
        if (obstacleGrid[i][j] == 1) {
          f[j] = 0;
          continue;
        }
        if (j - 1 >= 0 && obstacleGrid[i][j - 1] == 0) {
          f[j] += f[j - 1];
        }
      }
    }
    return f.back();
  }
};